#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<unordered_map>
#include<algorithm>
#include<chrono>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=2e5+1000;
typedef long long LL;
inline LL read(){LL x=0,f=1;char ch=getchar();	while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;}
LL a[maxn];
struct custom_hash {
    static uint64_t splitmix64(uint64_t x) {
        // http://xorshift.di.unimi.it/splitmix64.c
        x += 0x9e3779b97f4a7c15;
        x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
        x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
        return x ^ (x >> 31);
    }

    size_t operator()(uint64_t x) const {
        static const uint64_t FIXED_RANDOM = chrono::steady_clock::now().time_since_epoch().count();
        return splitmix64(x + FIXED_RANDOM);
    }
};
unordered_map<LL,LL,custom_hash>map1;
int main(void)
{
  vector<LL>v;
  for(LL i=1; ;i++){
    if(i*i>1e7) break;
    v.push_back(i*i);
  }
  //cout<<v.size()<<"\n";
  LL t;t=read();
  while(t--){
    map1.clear();
    LL n,k;n=read();k=read();
    for(LL i=1;i<=n;i++){
        a[i]=read();
    }
    if(n==1){
        printf("1\n");
        continue;
    }
    LL ans=0;
    map1[a[1]]++;
    ans++;
    for(int i=2;i<=n;i++){
        bool flag=1;
        for(LL j=0;j<v.size();j++){
            if( map1.count(v[j]/a[i]) ){
                LL temp=v[j]/a[i];
     //           debug(temp);
                if(temp*a[i]!=v[j]) continue;
      //          debug(v[j]);
      ///          debug(i);
                flag=0;
                break;
            }
        }
        if(flag==1){
            map1[a[i]]++;
        }
        else ans++,map1.clear(),map1[a[i]]++;
    }
    printf("%d\n",ans);
  }
return 0;
}
